package OptimalAlgorithm.DivideAndConquer_Merge;
//https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/
public class ReversePairs_One {
    public int reversePairs(int[] nums) {
        return mergeSort(nums,0,nums.length - 1);
    }
    //左半部分找 -> 左排序 -> 右半部分找 -> 右排序 -> 一左一右找数字 -> 整个区间排序
    //结果为左 + 右 + 一左一右
    private int mergeSort(int[] nums, int left,int right){
        if(left >= right){
            return 0;
        }
        int mid = (left + right) / 2;
        int a = mergeSort(nums,left,mid);
        int b = mergeSort(nums,mid + 1,right);
        int c = merge(nums,left,mid,right);
        return a + b + c;
    }
    //找一左一右找数字，策略1：固定右边数字，在左边找有多少比它大（数字升序）
/*    private int merge(int[] nums,int left, int mid,int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int index = 0;
        int ret = 0;
        int[] temp = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2){
            if(nums[s1] > nums[s2]){
                temp[index] = nums[s2];
                ret += e1 - s1 + 1;
                index++;
                s2++;
            }else {
                temp[index++] = nums[s1++];
            }
        }
        while (s1 <= e1){
            temp[index++] = nums[s1++];
        }
        while (s2 <= e2){
            temp[index++] = nums[s2++];
        }
        for (int i = left; i <= right ; i++) {
            nums[i] = temp[i - left];
        }
        return ret;
    }*/
    //找一左一右找数字，策略2：固定左边数字，在右边找有多少比它小（数字降序）
    private int merge(int[] nums,int left, int mid,int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int index = 0;
        int ret = 0;
        int[] temp = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2){
            if(nums[s1] > nums[s2]){
                temp[index] = nums[s1];
                ret += e2 - s2 + 1;
                index++;
                s1++;
            }else {
                temp[index++] = nums[s2++];
            }
        }
        while (s1 <= e1){
            temp[index++] = nums[s1++];
        }
        while (s2 <= e2){
            temp[index++] = nums[s2++];
        }
        for (int i = left; i <= right ; i++) {
            nums[i] = temp[i - left];
        }
        return ret;
    }
}
